home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / PCB_DESI / 1540.ZIP / PCBCA110.ZIP / SOLVE.C < prev    next >
C/C++ Source or Header  |  1990-11-18  |  16KB  |  490 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #ifndef VMS
  5. #include <fcntl.h>
  6. #include <io.h>
  7. #endif
  8.  
  9. #include "cell.h"
  10.  
  11. #ifndef ONESIDE
  12. #ifndef TWOSIDES
  13. error -- must define ONESIDE or TWOSIDES
  14. #endif
  15. #endif
  16.  
  17. #ifdef ONESIDE
  18. #ifdef TWOSIDES
  19. error -- must define ONESIDE or TWOSIDES, but not both
  20. #endif
  21. #endif
  22.  
  23. /*
  24. ** visit neighboring cells like this (where [9] is on the other side):
  25. **
  26. **    +---+---+---+
  27. **    | 1 | 2 | 3 |
  28. **    +---+---+---+
  29. **    | 4 |[9]| 5 |
  30. **    +---+---+---+
  31. **    | 6 | 7 | 8 |
  32. **    +---+---+---+
  33. */
  34.  
  35. static int delta[8][2] = { /* for visiting neighbors on the same side */
  36.      {  1, -1 }, /* northwest    */
  37.      {  1,  0 }, /* north        */
  38.      {  1,  1 }, /* northeast    */
  39.      {  0, -1 }, /* west        */
  40.      {  0,  1 }, /* east        */
  41.      { -1, -1 }, /* southwest    */
  42.      { -1,  0 }, /* south        */
  43.      { -1,  1 }  /* southeast    */
  44.     };
  45.  
  46. static int ndir[8] = { /* for building paths back to source */
  47.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  48.      FROM_EAST,                  FROM_WEST,
  49.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  50.     };
  51.  
  52. /* blocking masks for neighboring cells */
  53. #define BLOCK_NORTHEAST        ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  54.                 | ANGLE_NEtoSE | ANGLE_NWtoNE \
  55.                 | SHARP_NtoNE | SHARP_EtoNE | HOLE )
  56. #define BLOCK_SOUTHEAST        ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  57.                 | ANGLE_NEtoSE | ANGLE_SEtoSW \
  58.                 | SHARP_EtoSE | SHARP_StoSE | HOLE )
  59. #define BLOCK_SOUTHWEST        ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  60.                 | ANGLE_SEtoSW | ANGLE_SWtoNW \
  61.                 | SHARP_StoSW | SHARP_WtoSW | HOLE )
  62. #define BLOCK_NORTHWEST        ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  63.                 | ANGLE_SWtoNW | ANGLE_NWtoNE \
  64.                 | SHARP_WtoNW | SHARP_NtoNW | HOLE )
  65. #define BLOCK_NORTH        ( LINE_VERTICAL | BENT_NtoSE | BENT_NtoSW \
  66.                 | BENT_EtoNW | BENT_WtoNE \
  67.                 | BENT_StoNE | BENT_StoNW \
  68.                 | CORNER_NORTHEAST | CORNER_NORTHWEST \
  69.                 | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_NWtoNE \
  70.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  71.                 | SHARP_NtoNE | SHARP_NtoNW \
  72.                 | SHARP_EtoNE | SHARP_WtoNW | HOLE )
  73. #define BLOCK_EAST        ( LINE_HORIZONTAL | BENT_EtoSW | BENT_EtoNW \
  74.                 | BENT_NtoSE | BENT_StoNE \
  75.                 | BENT_WtoNE | BENT_WtoSE \
  76.                 | CORNER_NORTHEAST | CORNER_SOUTHEAST \
  77.                 | ANGLE_NEtoSE | ANGLE_SEtoSW | ANGLE_NWtoNE \
  78.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  79.                 | SHARP_EtoNE | SHARP_EtoSE \
  80.                 | SHARP_NtoNE | SHARP_StoSE | HOLE )
  81. #define BLOCK_SOUTH        ( LINE_VERTICAL | BENT_StoNE | BENT_StoNW \
  82.                 | BENT_EtoSW | BENT_WtoSE \
  83.                 | BENT_NtoSE | BENT_NtoSW \
  84.                 | CORNER_SOUTHEAST | CORNER_SOUTHWEST \
  85.                 | ANGLE_NEtoSE | ANGLE_SWtoNW | ANGLE_SEtoSW \
  86.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  87.                 | SHARP_StoSE | SHARP_StoSW \
  88.                 | SHARP_EtoSE | SHARP_WtoSW | HOLE )
  89. #define BLOCK_WEST        ( LINE_HORIZONTAL | BENT_WtoNE | BENT_WtoSE \
  90.                 | BENT_NtoSW | BENT_StoNW \
  91.                 | BENT_EtoSW | BENT_EtoNW \
  92.                 | CORNER_SOUTHWEST | CORNER_NORTHWEST \
  93.                 | ANGLE_SWtoNW | ANGLE_SEtoSW | ANGLE_NWtoNE \
  94.                 | DIAG_NEtoSW | DIAG_SEtoNW \
  95.                 | SHARP_WtoSW | SHARP_WtoNW \
  96.                 | SHARP_NtoNW | SHARP_StoSW | HOLE )
  97.  
  98. struct block {
  99.     int r1, c1;
  100.     long b1;
  101.     int r2, c2;
  102.     long b2;
  103.     };
  104.  
  105. static struct block blocking[8] = { /* blocking masks for diagonal traces */
  106.      {  0, -1, BLOCK_NORTHEAST,  1, 0, BLOCK_SOUTHWEST },
  107.      {  0,  0, 0, 0, 0, 0 },
  108.      {  1,  0, BLOCK_SOUTHEAST,  0, 1, BLOCK_NORTHWEST },
  109.      {  0,  0, 0, 0, 0, 0 },
  110.      {  0,  0, 0, 0, 0, 0 },
  111.      {  0, -1, BLOCK_SOUTHEAST, -1, 0, BLOCK_NORTHWEST },
  112.      {  0,  0, 0, 0, 0, 0 },
  113.      { -1,  0, BLOCK_NORTHEAST,  0, 1, BLOCK_SOUTHWEST }
  114.     };
  115.  
  116. static long blocking2[8] = { /* blocking masks for drilling vias */
  117.      BLOCK_SOUTHEAST, BLOCK_SOUTH, BLOCK_SOUTHWEST,
  118.      BLOCK_EAST,                   BLOCK_WEST,
  119.      BLOCK_NORTHEAST, BLOCK_NORTH, BLOCK_NORTHWEST
  120.     };
  121.  
  122. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  123.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  124.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  125.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  126.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  127.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  128.     };
  129.  
  130. /* mask for hole-related blocking effects */
  131. static struct {
  132.     long trace;
  133.     int present;
  134.     } selfok2[8] = {
  135.      { HOLE_NORTHWEST, 0 },
  136.      { HOLE_NORTH, 0 },
  137.      { HOLE_NORTHEAST, 0 },
  138.      { HOLE_WEST, 0 },
  139.      { HOLE_EAST, 0 },
  140.      { HOLE_SOUTHWEST, 0 },
  141.      { HOLE_SOUTH, 0 },
  142.      { HOLE_SOUTHEAST, 0 }
  143.     };
  144.  
  145. static long newmask[8] = { /* patterns to mask out in neighbor cells */
  146.     0, CORNER_NORTHWEST|CORNER_NORTHEAST, 0,
  147.     CORNER_NORTHWEST|CORNER_SOUTHWEST, CORNER_NORTHEAST|CORNER_SOUTHEAST,
  148.     0, CORNER_SOUTHWEST|CORNER_SOUTHEAST, 0
  149.     };
  150.  
  151. static char fmt[] =
  152.   "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";
  153.  
  154. extern int Nrows, Ncols; /* board dimensions */
  155.  
  156. /* measures of progress */
  157. extern int Ntotal;
  158. int Ncurrent = 0;
  159.  
  160. /* search statistics */
  161. extern long OpenNodes; /* total number of nodes opened */
  162. extern long ClosNodes; /* total number of nodes closed */
  163. extern long MoveNodes; /* total number of nodes moved */
  164. extern long MaxNodes; /* maximum number of nodes opened at one time */
  165.  
  166. extern void GetWork( int *, int *, char far * far *, int *, int *,
  167.     char far * far * );
  168. extern void InitQueue( void );
  169. extern void GetQueue( int *, int *, int *, int *, int * );
  170. extern void SetQueue( int, int, int, int, int, int, int );
  171. extern void ReSetQueue( int, int, int, int, int, int, int );
  172. extern long GetCell( int, int, int );
  173. extern void SetCell( int, int, int, long );
  174. extern void OrCell( int, int, int, long );
  175. extern int GetDir( int, int, int );
  176. extern void SetDir( int, int, int, int );
  177. extern int GetDist( int, int, int );
  178. extern void SetDist( int, int, int, int );
  179. extern int GetApxDist( int, int, int, int );
  180. extern int CalcDist( int, int, int );
  181.  
  182. void Solve( void );
  183. void Retrace( int, int, int, int, int );
  184.  
  185. void Solve () { /* route all traces */
  186.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc;
  187. #ifdef TWOSIDES
  188.     int skip;
  189. #endif
  190.     register int i;
  191.     char far *n1;
  192.     char far *n2;
  193.     long curcell, newcell, buddy, lastopen, lastclos, lastmove;
  194.     int newdist, olddir, success, self, echo;
  195.  
  196.     printf( "enter Solve()\n" );
  197.     echo = isatty( fileno(stdout) ) ? 1 : 0;
  198.     /* go until no more work to do */
  199.     for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  200.             GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  201.         Ncurrent++;
  202.         printf( "routing %Fs=%Fs, %d of %d\n", n1, n2, Ncurrent,
  203.             Ntotal );
  204.         if (r1 == r2 && c1 == c2) /* trivial case; already routed */
  205.             continue;
  206.         success = 0;
  207.         lastopen = lastclos = lastmove = 0;
  208.         InitQueue(); /* initialize the search queue */
  209.         a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
  210.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  211. #ifdef TWOSIDES
  212.         SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  213. #endif
  214.         /* search until success or we exhaust all possibilities */
  215.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  216.             GetQueue( &r, &c, &s, &d, &a )) {
  217.             if (r == r2 && c == c2) { /* success! */
  218.                 Retrace( r1, c1, r2, c2, s ); /* lay traces */
  219.                 success++;
  220.                 break;
  221.                 }
  222.             /* report every 100 new nodes or so */
  223.             if (echo && (OpenNodes - lastopen > 100
  224.                 || ClosNodes - lastclos > 100
  225.                 || MoveNodes - lastmove > 100)) {
  226.                 lastopen = (OpenNodes/100)*100;
  227.                 lastclos = (ClosNodes/100)*100;
  228.                 lastmove = (MoveNodes/100)*100;
  229.                 printf( fmt, OpenNodes, ClosNodes,
  230.                     MoveNodes, MaxNodes,
  231.                     (ClosNodes*50)/(Nrows*Ncols) );
  232.                 putchar( '\r' );
  233.                 }
  234.             curcell = GetCell( r, c, s );
  235.             if (curcell&HOLE) {
  236.                 self = 5;
  237.                 /* set 'present' bits */
  238.                 for (i = 0; i < 8; i++)
  239.                     selfok2[i].present =
  240.                     ((curcell&selfok2[i].trace)?1:0);
  241.                 }
  242.             else if (curcell & CORNER_NORTHWEST)
  243.                 self = 1;
  244.             else if (curcell & CORNER_NORTHEAST)
  245.                 self = 2;
  246.             else if (curcell & CORNER_SOUTHWEST)
  247.                 self = 3;
  248.             else if (curcell & CORNER_SOUTHEAST)
  249.                 self = 4;
  250.             else
  251.                 self = 0;
  252.             for (i = 0; i < 8; i++) { /* consider neighbors */
  253.                 /* check self-block */
  254.                 if (self < 5 && !selfok[self][i])
  255.                     continue;
  256.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  257.                     || (nc = c+delta[i][1]) < 0
  258.                     || nc >= Ncols) /* off the edge? */
  259.                     continue;
  260.                 if (self == 5 && selfok2[i].present)
  261.                     continue;
  262.                 newcell = GetCell( nr, nc, s );
  263.                 /* check for non-target hole */
  264.                 if (newcell & HOLE) {
  265.                     if (nr != r2 || nc != c2)
  266.                         continue;
  267.                     }
  268.                 /* check for traces */
  269.                 else if (newcell & ~(newmask[i]))
  270.                     continue;
  271.                 /* check blocking on corner neighbors */
  272.                 if (delta[i][0] && delta[i][1]) {
  273.                     /* check first buddy */
  274.                     buddy = GetCell( r+blocking[i].r1,
  275.                         c+blocking[i].c1, s );
  276.                     if (buddy & (blocking[i].b1))
  277.                         continue;
  278.                     /* check second buddy */
  279.                     buddy = GetCell( r+blocking[i].r2,
  280.                         c+blocking[i].c2, s );
  281.                     if (buddy & (blocking[i].b2))
  282.                         continue;
  283.                     }
  284.                 olddir = GetDir( r, c, s );
  285.                 newdist = d+CalcDist( ndir[i], olddir,
  286.                     (olddir == FROM_OTHERSIDE)
  287.                     ? GetDir( r, c, 1-s ) : 0 );
  288.                 /* if (a) not visited yet, or (b) we have */
  289.                 /* found a better path, add it to queue */
  290.                 if (!GetDir( nr, nc, s )) {
  291.                     SetDir( nr, nc, s, ndir[i] );
  292.                     SetDist( nr, nc, s, newdist );
  293.                     SetQueue( nr, nc, s, newdist,
  294.                         GetApxDist( nr, nc, r2, c2 ),
  295.                         r2, c2 );
  296.                     }
  297.                 else if (newdist < GetDist( nr, nc, s )) {
  298.                     SetDir( nr, nc, s, ndir[i] );
  299.                     SetDist( nr, nc, s, newdist );
  300.                     ReSetQueue( nr, nc, s, newdist,
  301.                         GetApxDist( nr, nc, r2, c2 ),
  302.                         r2, c2 );
  303.                     }
  304.                 }
  305. #ifdef TWOSIDES
  306.             /* consider other side of board */
  307.             olddir = GetDir( r, c, s );
  308.             if (olddir == FROM_OTHERSIDE)
  309.                 continue; /* useless move, so don't bother */
  310.             if (curcell) /* can't drill via if anything here */
  311.                 continue;
  312.             /* check for holes or traces on other side */
  313.             if (newcell = GetCell( r, c, 1-s ))
  314.                 continue;
  315.             /* check for nearby holes or traces on both sides */
  316.             for (skip = i = 0; i < 8; i++) {
  317.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  318.                     || (nc = c+delta[i][1]) < 0
  319.                     || nc >= Ncols) /* off the edge? */
  320.                     continue;
  321.                 if (GetCell( nr, nc, s ) & blocking2[i]) {
  322.                     skip = 1; /* can't drill via here */
  323.                     break;
  324.                     }
  325.                 if (GetCell( nr, nc, 1-s ) & blocking2[i]) {
  326.                     skip = 1; /* can't drill via here */
  327.                     break;
  328.                     }
  329.                 }
  330.             if (skip) /* neighboring hole or trace? */
  331.                 continue; /* yes, can't drill via here */
  332.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir, 0 );
  333.             /* if (a) not visited yet, or (b) we have found a
  334.             /* better path, add it to queue */
  335.             if (!GetDir( r, c, 1-s )) {
  336.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  337.                 SetDist( r, c, 1-s, newdist );
  338.                 SetQueue( r, c, 1-s, newdist, a, r2, c2 );
  339.                 }
  340.             else if (newdist < GetDist( r, c, 1-s )) {
  341.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  342.                 SetDist( r, c, 1-s, newdist );
  343.                 ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
  344.                 }
  345. #endif /* TWOSIDES */
  346.             }
  347.         printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
  348.             (ClosNodes*50)/(Nrows*Ncols) );
  349.         putchar( '\n' );
  350.         if (!success)
  351.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  352.         /* clear direction flags */
  353.         for (r = 0; r < Nrows; r++) {
  354.             for (c = 0; c < Ncols; c++) {
  355.                 SetDir( r, c, TOP, FROM_NOWHERE );
  356.                 SetDir( r, c, BOTTOM, FROM_NOWHERE );
  357.                 }
  358.             }
  359.         }
  360.     printf( "leave Solve()\n" );
  361.     }
  362.  
  363. static long bit[8][9] = { /* OT=Otherside */
  364.      /* N, NE, E, SE, S, SW, W, NW, OT */
  365. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
  366.        SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
  367. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
  368.        0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
  369. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  370.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
  371. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
  372.        ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
  373. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
  374.        BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
  375. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
  376.        BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
  377. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
  378.        BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
  379. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  380.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
  381.     };
  382.  
  383. void Retrace ( rr1, cc1, rr2, cc2, s )
  384.     /* work from target back to source, actually laying the traces */
  385.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  386.     {
  387.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  388.     register int x, y;
  389.     long b;
  390.  
  391.     r1 = rr2;
  392.     c1 = cc2;
  393.     s1 = s;
  394.     r0 = c0 = s0 = ILLEGAL;
  395.     do {
  396.         /* find where we came from to get here */
  397.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  398.         case FROM_NORTH:    r2++;        break;
  399.         case FROM_EAST:            c2++;    break;
  400.         case FROM_SOUTH:    r2--;        break;
  401.         case FROM_WEST:            c2--;    break;
  402.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  403.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  404.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  405.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  406.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  407.         default:
  408.             fprintf( stderr, "internal error: no way back\n" );
  409.             exit( -1 );
  410.             break;
  411.             }
  412.         if (r0 != ILLEGAL)
  413.             y = GetDir( r0, c0, s0 );
  414.         /* see if target or hole */
  415.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  416.             switch (x) {
  417.             case FROM_NORTH:
  418.                 OrCell( r1, c1, s1, HOLE_NORTH );    break;
  419.             case FROM_EAST:
  420.                 OrCell( r1, c1, s1, HOLE_EAST );    break;
  421.             case FROM_SOUTH:
  422.                 OrCell( r1, c1, s1, HOLE_SOUTH );    break;
  423.             case FROM_WEST:
  424.                 OrCell( r1, c1, s1, HOLE_WEST );    break;
  425.             case FROM_NORTHEAST:
  426.                 OrCell( r1, c1, s1, HOLE_NORTHEAST );    break;
  427.             case FROM_SOUTHEAST:
  428.                 OrCell( r1, c1, s1, HOLE_SOUTHEAST );    break;
  429.             case FROM_SOUTHWEST:
  430.                 OrCell( r1, c1, s1, HOLE_SOUTHWEST );    break;
  431.             case FROM_NORTHWEST:
  432.                 OrCell( r1, c1, s1, HOLE_NORTHWEST );    break;
  433.             case FROM_OTHERSIDE:
  434.             default:
  435.                 fprintf( stderr, "internal error\n" );
  436.                 exit( -1 );
  437.                 break;
  438.                 }
  439.             }
  440.         else {
  441.             if ((y == FROM_NORTH || y == FROM_NORTHEAST
  442.                 || y == FROM_EAST || y == FROM_SOUTHEAST
  443.                 || y == FROM_SOUTH || y == FROM_SOUTHWEST
  444.                 || y == FROM_WEST || y == FROM_NORTHWEST)
  445.                 && (x == FROM_NORTH || x == FROM_NORTHEAST
  446.                 || x == FROM_EAST || x == FROM_SOUTHEAST
  447.                 || x == FROM_SOUTH || x == FROM_SOUTHWEST
  448.                 || x == FROM_WEST || x == FROM_NORTHWEST
  449.                 || x == FROM_OTHERSIDE)
  450.                 && (b = bit[y-1][x-1])) {
  451.                 OrCell( r1, c1, s1, b );
  452.                 if (b & HOLE)
  453.                     OrCell( r2, c2, s2, HOLE );
  454.                 }
  455.             else {
  456.                 fprintf( stderr, "internal error\n" );
  457.                 exit( -1 );
  458.                 }
  459.             }
  460.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  461.             switch (x) {
  462.             case FROM_NORTH:
  463.                 OrCell( r2, c2, s2, HOLE_SOUTH );    break;
  464.             case FROM_EAST:
  465.                 OrCell( r2, c2, s2, HOLE_WEST );    break;
  466.             case FROM_SOUTH:
  467.                 OrCell( r2, c2, s2, HOLE_NORTH );    break;
  468.             case FROM_WEST:
  469.                 OrCell( r2, c2, s2, HOLE_EAST );    break;
  470.             case FROM_NORTHEAST:
  471.                 OrCell( r2, c2, s2, HOLE_SOUTHWEST );    break;
  472.             case FROM_SOUTHEAST:
  473.                 OrCell( r2, c2, s2, HOLE_NORTHWEST );    break;
  474.             case FROM_SOUTHWEST:
  475.                 OrCell( r2, c2, s2, HOLE_NORTHEAST );    break;
  476.             case FROM_NORTHWEST:
  477.                 OrCell( r2, c2, s2, HOLE_SOUTHEAST );    break;
  478.             case FROM_OTHERSIDE:
  479.             default:
  480.                 fprintf( stderr, "internal error\n" );
  481.                 exit( -1 );
  482.                 break;
  483.                 }
  484.             }
  485.         /* move to next cell */
  486.         r0 = r1; c0 = c1; s0 = s1;
  487.         r1 = r2; c1 = c2; s1 = s2;
  488.         } while (!(r2 == rr1 && c2 == cc1));
  489.     }
  490.